package com.nowc.ex.e142;

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class c {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        in.nextToken();
        int n = (int) in.nval;

        in.nextToken();
        int m = (int) in.nval;

        int[] arr = new int[n * 2];

        // 2 1 0 3 0 1 2 . 2 1 0 3 0 1 2
        for (int i = 0; i < n; i++) {
            in.nextToken();
            arr[i] = (int) in.nval;
            arr[i + n] = (int) in.nval;
        }

        List<Integer>[] occ = new ArrayList[m];
        for (int v = 0; v < m; v++) {
            occ[v] = new ArrayList<>();
        }
        for (int i = 0; i < 2 * n; i++) {
            occ[arr[i]].add(i);
        }

        // —— 指针数组 & 首次出现位置 ——
        int[] idx = new int[m];
        int[] pos = new int[m];
        for (int v = 0; v < m; v++) {
            idx[v] = 0;
            pos[v] = occ[v].get(0);
        }

        boolean[] valid = new boolean[m - 1];
        int badCount = 0;
        for (int u = 0; u < m - 1; u++) {
            valid[u] = pos[u] < pos[u + 1];
            if (!valid[u]) badCount++;
        }

        int ans = 0;
        for (int k = 0; k < n; k++) {
            if (badCount == 0) ans++;

            int v = arr[k];

            for (int u : new int[] { v - 1, v}) {
                if (u >= 0 && u < m - 1) {
                    if (!valid[u]) badCount--;
                }
            }
            idx[v]++;
            pos[v] = occ[v].get(idx[v]);

            for (int u : new int[] { v - 1, v}) {
                if (u >= 0 && u < m - 1) {
                    valid[u] = pos[u] < pos[u + 1];
                    if (!valid[u]) badCount++;
                }
            }
        }
        out.println(ans);
        out.flush();
    }
}